package LeetCode;

import java.util.ArrayList;

public class SpiralMatrix
{
  //pass both
  public ArrayList<Integer> spiralOrder(int[][] matrix) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(matrix.length == 0)
      return result;
    if(matrix[0].length == 0)
      return result;
    print_spiral(matrix, matrix.length, matrix[0].length, 0, result);
    return result;
  }
  
  public static void print_spiral(int mat[][], int m, int n, int k, ArrayList<Integer> result) {
    if (m <= 0 || n <= 0)
      return;
    if (m == 1) {
      for (int j = 0; j < n; j++)
        result.add(mat[k][k + j]);
      return;
    }
    if (n == 1) {
      for (int i = 0; i < m; i++)
        result.add(mat[k + i][k]);
      return;
    }
    // print from top left
    for (int j = 0; j < n - 1; j++)
      result.add(mat[k][k + j]);
    // print from top right
    for (int i = 0; i < m - 1; i++)
      result.add(mat[k + i][k + n - 1]);
    // print from bottom right
    for (int j = 0; j < n - 1; j++)
      result.add(mat[k + m - 1][k + n - 1 - j]);
    // print from bottom left
    for (int i = 0; i < m - 1; i++)
      result.add(mat[k + m - 1 - i][k]);
    print_spiral(mat, m - 2, n - 2, k + 1, result);
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
